1. Technical Field
The present invention relates in general to snoop operations in multiprocessor systems and in particular to snoop operations initiated by one device which are retried by another device in a multiprocessor system. Still more particularly, the present invention relates to making forward progress towards an ultimate state on retried snoop operations in order to allow other traffic to proceed and alleviate the prospect of a livelock.
2. Description of the Related Art
Contemporary data processing systems employ multiple processors, multilevel cache hierarchies, or both to improve performance. A conventional symmetric multiprocessor (SMP) system employs several processing elements, which may include a processor and one or more levels of cache memory, connected via a common system bus which also couples the processing elements to any additional cache memories and to system memory. In such SMP systems, each processing element is capable of acting as a system bus master, initiating bus operations affecting the storage hierarchy. Cache controllers for additional caches in the storage hierarchy are also capable of acting as the system bus master, and of snooping bus operations initiated by other devices connected to the system bus. Devices may also intervene in snooped bus operations in order to maintain a coherent memory hierarchy.
The coherency of the storage hierarchy is maintained through the use of a selected memory coherency protocol such as the MESI protocol. In the MESI protocol, an indication of a coherency state is stored in association with each coherency granule (e.g. cache line or sector) of at least all upper level cache memories. The coherency state, which is indicated by bits in the cache directory, denotes the condition of the cache entry with respect to the same data stored in system memory: modified (M), exclusive (E), shared (S), or invalid (I) in the basic MESI coherency protocol. The modified state indicates that cache data has been modified with respect to corresponding data in system memory without also modifying the system memory data, such that the only valid copy of the data is within the cache entry storing the modified cache line or sector. The exclusive state indicates that the cache entry is consistent with system memory but is only found, within all caches at that level of the storage hierarchy, in the subject cache. The shared state indicates that the cache entry may be found in the subject cache and at least one other cache at the same level in the storage hierarchy, with all copies of the data being consistent with the corresponding data in system memory. Finally, the invalid state indicates that a cache entry--both the data and the address tag--within a given cache is no longer coherent with either system memory or other caches in the storage hierarchy.
Modifications of the basic MESI protocol may add additional states--possibly at the expense of additional bits of overhead in the cache directories--conveying other information regarding the condition of cache data as compared to corresponding data in system memory. For example, the R-MESI protocol adds the recent (R) state, essentially a variant of the shared state indicating that the cache entry may be found in both the subject cache and at least one other cache at the same level in the storage hierarchy and that all copies of the data in the subject cache and other caches are consistent with the corresponding data in system memory, but also indicating that the subject cache, of all caches containing the shared data, most recently received the data in a system bus transaction such as a read from system memory. The R state is more fully described in U.S. patent application Ser. No. 08/839,557, which is incorporated in its entirety herein by reference. Another additional coherency state which may be added to the basic MESI coherency protocol is the hovering (H) state, which indicates that an address tag stored in the tag field of a cache entry is valid but that the associated data item (e.g. cache line or cache sector) is invalid. The H state is described in greater detail in U.S. patent application Ser. No. 09/024,610 (Docket No. AT9-97-410), which is also incorporated in its entirety herein by reference.
Devices such as processors and cache controllers may intervene in snooped bus operations in order to preserve data integrity within the storage hierarchy. For example, where one device initiates a read or read with intent to modify (rwitm) request for specified data which is resident within a second device in the modified state, the second device intervenes in the bus operation for the purpose of sourcing the modified data to the requesting device (a "modified intervention"). Similarly, where data requested by a read or rwitm bus operation is resident within a device in the recent state, the device intervenes with the requested data (a "shared intervention"). In both cases, the snooping device which intervened determined that it should respond to the read or rwitm request (referred to as a "snoop hit"). In either case, however, a third device which was also snooping system bus transactions may retry the initial bus operation, effectively killing both the request and the responsive intervention.
In current designs, an intervention is typically halted with no change in coherency state when the read or rwitm request is retried, with the intervening device sourcing data when the requests ceases being retried. Processing resources are thus effectively wasted by retried snoop hits, which result in no progress being made toward achieving the data transfer which was the ultimate object of the original request. Furthermore, in some instances a pattern may develop of read or rwitm requests being repeatedly initiated and repeatedly retried without any change in the circumstances which caused the request to be retried. Such events, referred to as "livelocks," result in two or more system devices interfering with each other with no useful work being accomplished. Like endless loops, livelocks must generally be broken by external intercession.
It would be desirable, therefore, to provide a mechanism for making progress on retried snoop hits toward an ultimate resolution of the bus operations being retried. It would further be desirable for the mechanism to aid in preventing livelocks and to free snoop queues for other snoop operations.